package cre.sample.test.ds.array;

/**
 * 这个是自定义的容器类，有序数组
 * Created by CreGu on 2016/5/25.
 */
public class OrderArray {
    private long[] arr;
    /**
     * 当前数量
     */
    private int elements;

    public OrderArray(int size) {
        arr = new long[size];
        elements = 0;
    }

    /**
     * 得排序
     *
     * @param element
     */
    public void insert(long element) {
        int i;
        for (i = 0; i < elements ; i++) {
            if (arr[i] > element) {
                break;
            }
        }

        for (int j = i; j < elements; j++) {
            arr[j + 1] = arr[j];
        }
        arr[i] = element;
        elements++;
    }

    /**
     * 有序数组，可以用二分查找
     *
     * @param element
     * @return
     */
    private int findInternal(long element) {
        int start = 0;
        int end = arr.length - 1;

        while (true) {
            int curr = (start + end) / 2;
            if (arr[curr] == element) {
                return curr;
            }

            if (start > end) {
                return -1;
            }

            if (arr[curr] < element) {
                start = curr + 1;
            } else {
                end = curr - 1;
            }
        }
    }

    public boolean find(long element) {
        return findInternal(element) != -1;
    }

    public boolean delete(long element) {
        int i = findInternal(element);

        if (i != -1) {
            for (int j = i; j < elements - 1; j++) {
//           后面的覆盖前面的
                arr[j] = arr[j + 1];
            }
            elements--;
            return true;
        } else {
            return false;
        }
    }

    public void display() {
        for (int i = 0; i < elements; i++) {
            System.out.println(arr[i]);
        }
    }
}
